/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-break-iii
   @Language: C++
   @Datetime: 19-06-19 09:21
   */


class Solution {
public:
	/*
	 * @param : A string
	 * @param : A set of word
	 * @return: the number of possible sentences.
	 */
	int wordBreak3(string& s, unordered_set<string>& dict) {
		// Write your code here
		if(s.length()==0 || dict.size()==0) return 0;
		for(int i=s.length(); i--; s[i]=tolower(s[i]));
		unordered_set<string> words;
		for(auto w:dict){
			for(int i=w.length(); i--; w[i]=tolower(w[i]));
			words.insert(w);
		}
		vector<int> dp(s.length()+1,0);
		dp[0]=1;
		for(int len=1; len<=s.length(); ++len){
			for(int i=len, j=1; i--; ++j){
				string t=s.substr(i,j);
				if(words.count(t)) dp[len]+=dp[i];
			}
		}
		return dp[s.length()];
	}
};
